﻿#define _CRT_SECURE_NO_WARNINGS

//给出一个整型数组 numbers 和一个目标值 target，请在数组中找出两个加起来等于目标值的数的下标，返回的下标按升序排列。
//（注：返回的数组下标从1开始算起，保证target一定可以由数组里面2个数字相加得到）
//
//数据范围：2\leq len(numbers) \leq 10 ^ 52≤len(numbers)≤10
//5
//， - 10 \leq numbers_i \leq 10 ^ 9−10≤numbers
//i
//​
//≤10
//9
//，0 \leq target \leq 10 ^ 90≤target≤10
//9
//
//要求：空间复杂度 O(n)O(n)，时间复杂度 O(nlogn)O(nlogn)
//示例1
//输入：
//[3, 2, 4], 6
//返回值：
//[2, 3]
//说明：
//因为 2 + 4 = 6 ，而 2的下标为2 ， 4的下标为3 ，又因为 下标2 < 下标3 ，所以返回[2, 3]
//    示例2
//    输入：
//    [20, 70, 110, 150], 90
//    返回值：
//    [1, 2]
//说明：
//20 + 70 = 90


int* twoSum(int* numbers, int numbersLen, int target, int* returnSize) {
    // write code here
    *returnSize = 2;
    static int arr[2] = { 0 };
    int i = 0;
    for (i = 0; i < numbersLen; i++)
    {
        if (numbers[i] > target)
            continue;
        int j = 0;
        for (j = i + 1; j < numbersLen; j++)
        {
            if ((numbers[i] + numbers[j]) == target)
            {
                arr[0] = i + 1;
                arr[1] = j + 1;
                break;
            }
        }
    }
    return arr;
}